package main

import (
	"fmt"
)

/**
执行用时：8 ms, 在所有 Go 提交中击败了35.69%的用户
内存消耗：5.6 MB, 在所有 Go 提交中击败了52.65%的用户
 */
func minDistance(a string, b string) int {

	n, m := len(a), len(b)
	a, b = " " + a, " " + b

	f := make([][]int, n + 1)
	for i := 0; i <= n; i++ { f[i] = make([]int, m + 1) }

	for i := 0; i <= m; i++ { f[0][i] = i }
	for i := 0; i <= n; i++ { f[i][0] = i }
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1
			if a[i] == b[j] {
				f[i][j] = min(f[i][j], f[i - 1][j - 1])
			} else {
				f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1)
			}
		}
	}

	return f[n][m]
}

// 求最小值
func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	fmt.Println(minDistance("horse", "ros"))  // 3
}
